package com.example.lcpractice.lc;

import java.util.*;

/**
 * 239. 滑动窗口最大值
 * <p>
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回 滑动窗口中的最大值 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 * 输出：[3,3,5,5,6,7]
 * 解释：
 * 滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 * 1 [3  -1  -3] 5  3  6  7       3
 * 1  3 [-1  -3  5] 3  6  7       5
 * 1  3  -1 [-3  5  3] 6  7       5
 * 1  3  -1  -3 [5  3  6] 7       6
 * 1  3  -1  -3  5 [3  6  7]      7
 * 示例 2：
 * <p>
 * 输入：nums = [1], k = 1
 * 输出：[1]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * 1 <= k <= nums.length
 */
public class Lc239 {


    public static void main(String[] args) {
//        System.out.println(Math.floor(Math.sqrt(99))==9);

        int[] ints = {1, 3, -1, -3, 1, 1, 2, 1};
        System.out.println(Arrays.toString(maxSlidingWindow2(ints, 3)));
    }

    //超时
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int[] re = new int[nums.length - k + 1];
        Queue<Integer> temp = new ArrayDeque<>();
        int tempMax = Integer.MIN_VALUE;
        //处理第一个滑动窗口
        for (int i = 0; i < k; i++) {
            temp.add(nums[i]);
            tempMax = Math.max(tempMax, nums[i]);
        }
        //第一个窗口最大
        re[0] = tempMax;
        //从第二个开始判断
        for (int i = k; i < nums.length; i++) {
            //必定队列出窗口最左边
            Integer pollOne = temp.poll();
            //如果 当前数值 大于上一个窗口最大 直接挤进去 并且 dp[i]=当前数字即可
            if (nums[i] >= tempMax || k == 1) {
                tempMax = nums[i];
                re[i - k + 1] = tempMax;
                temp.add(nums[i]);
            } else {
                //挤进去
                temp.add(nums[i]);
                //如果挤出来的先锋是最大值，那么要在窗内以及 当前数值比大
                if (pollOne == tempMax) {
                    tempMax = nums[i];
                    for (Integer integer : temp) {
                        tempMax = Math.max(tempMax, integer);
                    }
                }
                //如果没有挤出最大，只管挤进去当前数就够了，记得把以前的窗口最大赋值进来
                re[i - k + 1] = tempMax;
            }
        }
        return re;
    }

    public static int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        // 有限队列 每个队列装二维数组 指定排序方式   arr[0] nums[i]; arr[1] i本身 如果nums[i]相等，比较i大小 i越大越前，否则num[i]越大越前
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1]);
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        //结果由于滑动窗口把前(k-1)个和k个融合为1个
        int[] ans = new int[n - k + 1];
        //第一个窗口最大值
        ans[0] = pq.peek()[0];
        // i=k恰好第一个窗口右移动1位，即第2个窗口
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            int peekIndex = pq.peek()[1];
            int windowsLeftIndex = i - k;
            // pq.peek()[1]代表窗口最大值对应的 i1  小于等于   窗口最左值的i（此时窗口为k+1）
            // 也就是 即将移动出窗口的数是最大值( 新加的数字没有成为最大 && 旧的最大被窗口挤出去 )
            while (peekIndex <= windowsLeftIndex) {
                //挤出旧的最大
                pq.poll();
                peekIndex = pq.peek()[1];
            }
            //赋值当前ans位 的最大值  （利用优先队列特性）
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    public static int[] maxSlidingWindow3(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }
        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}
